package mutiyi;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Author:yang
 * Date:2024-03-06 11:49
 * 工具类：枚举全部选取最小值
 */
public class ShortPathUtil {

    /*
    计算两个点之间的距离：横坐标之差的平方+纵坐标之差的平方然后开根号
     */
    public static double calDistance(int[] point1, int[] point2) {
        return Math.sqrt(Math.pow(point1[0] - point2[0], 2) + Math.pow(point1[1] - point2[1], 2));
    }

    /*
    计算总距离
     */
    public static double calTotalDistance(List<int[]> pointsOrder) {
        double totalDistance = 0;
        int n = pointsOrder.size();

        // 遍历传入的点
        for (int i = 0; i < n - 1; i++) {
            // 当前点与后一个点计算距离
            totalDistance += calDistance(pointsOrder.get(i), pointsOrder.get(i + 1));
        }

        // 最后一个点与第一个点距离
        totalDistance += calDistance(pointsOrder.get(n - 1), pointsOrder.get(0));

        return totalDistance;
    }

    /*
    找到所有点排列组合后的最小距离值
     */
    public static double findShortDistance(List<int[]> points) {
        List<int[]> minRouter = null;
        double minDistance = Double.POSITIVE_INFINITY;

        // 所有点的组合排列
        List<List<int[]>> routers = router(points);

        for (List<int[]> router : routers) {
            // 计算当前组合的距离
            double currentDistance = calTotalDistance(router);
            // 比较选取最小组合
            if (currentDistance < minDistance) {
                minDistance = currentDistance;
                minRouter = router;
            }
        }

        minDistance = calTotalDistance(minRouter);

        return minDistance;
    }

    /*
    生成全部排列的集合
     */
    private static List<List<int[]>> router(List<int[]> points) {
        List<List<int[]>> result = new ArrayList<>();
        routerHelper(result, points, 0);
        return result;
    }

    /*
    递归生成排列组合
     */
    private static void routerHelper(List<List<int[]>> result, List<int[]> points, int index) {
        if (index == points.size()) {
            result.add(new ArrayList<>(points));
        }

        // 交换元素,生成不同的组合
        for (int i = index; i < points.size(); i++) {
            Collections.swap(points, i, index);
            routerHelper(result, points, index + 1);
            Collections.swap(points, i, index);
        }
    }

}
